package org.example;

import com.sun.org.apache.bcel.internal.generic.RET;

/**
 * Hello world!
 */
public class App {
    public static void main(String[] args) {
//        Integer[] a = {2, 4, 5, 0, 6, 8, 9, 1, 3, 7};
        int[] a = {2, 4, 5, 0, 6, 8, 9, 1, 3, 7};


        shellSort(a);

        for (int i : a) {
            System.out.println(i);
        }

    }


    public static void shellSort(int[] arr) {
        int gap = arr.length;
        while (gap > 1) {
            gap /= 2;
            shell(arr, gap);
        }
    }

    public static void shell(int[] arr, int gap) {
        if (arr == null) {
            return;
        }
        int tmp;

        for (int i = gap; i < arr.length; i++) {
            tmp = arr[i];
            for (int j = i - gap; j >= 0; j -= gap) { // 第一波：j= i-gap=0,
                if (arr[j] > tmp) {
                    arr[j + gap] = arr[j];//第一个数比较大，则把第一个数据放到，j+间隙上索引对应的数组上 （意思也就是往后放）
                    arr[j] = tmp; // 比较小的数据放到第一波的索引上
                } else {
                    break;
                }
            }
        }
    }

//    /**
//     * 希尔排序
//     * 时间复杂度：O（N^1.3~N^1.5）
//     * 空间复杂度：O（1）
//     * 稳定性：不稳定
//     *今天
//     * @param array
//     */
//    public static void shellSort(int[] array) {
//        int gap = array.length;
//        while (gap > 1) {
//            gap /= 2;
//            shell(array, gap);
//        }
//    }
//
//    private static void shell(int[] array, int gap) {
//        // 从小到大排序
//        if (array == null) {
//            return;
//        }
//        int tmp;
//        for (int i = gap; i < array.length; i++) {
//            tmp = array[i];
//            for (int j = i - gap; j >= 0; j -= gap) {
//
//                // j往后走
//                if (array[j] > tmp) {
//                    array[j + gap] = array[j];
//                    array[j] = tmp;
//                } else {
//                    break;
//                }
//            }
//        }
//    }

}
